\section{Ejemplos de uso en la vida real}

Un ejemplo posible de un problema interesante que puede modelarse en parte usando M\'inimo Conjunto Dominante
es:

\begin{quote}
	Se tiene una provincia que consiste en un conjunto de pueblos. Algunos de ellos estan conectados por rutas. Se sabe cuanto tiempo
	le toma a un veh\'iculo recorrer la autopista entre dos ciudades. Denominamos el tiempo (en minutos) que le toma a un veh\'iculo
	ir de la ciudad $i$ a la ciudad $j$ por autopista directa como $t_{ij}$.

	Para mejorar la calidad de vida de los habitantes, el gobernador decide instalar hospitales en algunos de los pueblos. Los habitantes
	de pueblos que no tienen hospitales podr\'an sin embargo pedir una ambulancia, que acudir\'a lo m\'as r\'apido posible siguiendo una 
	ruta \'optima y sin parar en pueblos intermedios, y partiendo del hospital m\'as cercano al pueblo de donde salio el pedido. 

	Sin embargo, esta el problema presupuesto, y el gobernador sabe que dispone de un presupuesto de $P$ millones de pesos,
	y que construir y equipar un hospital sale $C$ millones de pesos.

	Asumiendo se tienen todos los datos señalados ¿cu\'al es el m\'inimo tiempo de respuesta
	m\'aximo (es decir, el tiempo m\'as largo que le tomar\'ia, para un pueblo dado, llegar a una ambulancia que parte del pueblo m\'as
	cercano al primero que tiene un hospital) m\'as chico que se puede lograr?.
\end{quote}

Para resolver este problema podemos calcular (en primera instancia) el tiempo que tomaria ir de cada pueblo a cada otro pueblo (por ejemplo
usando el algoritmo de Floyd-Warshall). Armamos entonces un grafo $G$, donde cada nodo es un pueblo y hay una arista entre cada par de pueblos 
que tiene el tiempo m\'inimo para ir de uno al otro.

Luego, para determinar el m\'inimo tiempo de respuesta, hacemos b\'usqueda binaria en ese tiempo (los l\'imites los sabemos a priori: son 0 y
el tiempo m\'aximo de ir entre dos ciudades). Para saber si es posible responder con un tiempo de respuesta menor o igual que $t$, armamos
un nuevo grafo $H$ que tiene los mismos nodos que $G$ y que tiene todas las aristas de peso menor o igual que $t$.

Lo que queremos entonces es tomar un subconjunto $D$ de los nodos de este $H$ tal que todo nodo este en $D$ o sea vecino de alguien en $D$ (o sea,
que en todo pueblo haya un hospital o un lugar tiempo de respuesta directo menor o igual que $t$ tenga un hospital, por como armamos $H$).

El costo correspondiente va a ser $C \times | D |$, porque necesitamos construir un hospital en cada lugar. Si $C \times | D | \leq P$, entonces
se puede. 

Lo que queremos entonces, como $C$ y $P$ son fijos en nuestro modelo, es minimizar la cantidad de nodos de $D$. Para eso, usamos m\'inimo conjunto
dominante para obtenerlo.

Como se ve entonces, m\'inimo conjunto dominante aparece como subproblema de este problema en la soluci\'on elegida, incluso cuando
el problema a primera vista pareciera no tener nada que ver con el original.
